// https://www.lintcode.com/problem/the-sum-of-array/

public class Solution {
    /**
     * @param arr: An array
     * @return: An array
     */
    public int[] getSum(int[] arr) {
        // Write your code here.
        int[] ret = new int[arr.length];
        int[] arr_copy = new int[arr.length];
        System.arraycopy(arr, 0, arr_copy, 0, arr.length);
        Arrays.sort(arr);
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : arr) {
            map.put(a, 0);
        }
        for (int i = 1; i < arr.length; ++i) {
            map.put(arr[i], arr[i - 1] + map.get(arr[i - 1]));
        }
        for (int i = 0; i < arr_copy.length; ++i) {
            ret[i] = map.get(arr_copy[i]);
        }
        return ret;
    }
}